// m

// 给定一个包含n+1个整数的数组nums，里边包含的值都在1-n之间，假设nums中只存在一个重复的整数，要求找出这个重复的数
// 要求使用空间复杂度为常数级，时间复杂度小于O(n平方)的解决方法

// 思路：利用二分查找的思想，两个指针left和right，left指向1， right指向n
// 将区间[1,n]分为[left, mid]和[mid + 1, right]
// 对于中间数mid，统计nums中小于等于mid的数个数cnt，如果cnt < mid,则重复数一定不会出现在左侧区间，从右侧区间开始搜索
// 如果cnt大于mid，则重复数出现在左侧区间，则从左侧区间开始搜索
//

function findDuplicate(nums) {
    let n = nums.length
    let left = 1
    let right = n - 1
    while (left < right) {
        let mid = left + Math.floor((right - left) / 2)
        let cnt = 0
        for (let i = 0; i < nums.length; i++) {
            if (nums[i] <= mid) {
                cnt += 1
            }            
        }
        if (cnt <= mid) {
            left =  mid + 1
        } else {
            right = mid
        }
    }
    return left
}

let arr = [8,9,1, 2, 2,3,,4,5,6,7, 10]
console.log(findDuplicate(arr))